﻿// 0910train03.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <limits>
#include <iomanip>
#include <unordered_map>
#include <unordered_set>
#include <deque>

using namespace std;

/*
 示例 1：
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
 */
class Solution01 {
public:
    string minWindow(string s, string t) {

        string origin_str = s;
        string target_str = t;

        //统计目标char需要的数量
        vector<int>chracter_v(128);
        for (auto&target_ch:target_str)
        {
            chracter_v[target_ch] += 1;
        }

        int target_count = target_str.size();
        int left = 0;

        int window_start = 0;
        int window_length = origin_str.size() + 1;

        for (int right=0; right <origin_str.size(); right++)
        {
            char curr_ch = origin_str[right];
            if (chracter_v[curr_ch]>0)
            {
                //说明是目标字符
                target_count--;
            }
            chracter_v[curr_ch] -= 1;

            while (target_count==0)
            {
                //找到以后，更新window_length
                if (target_count==0)
                {
                    if (right-left+1<window_length)
                    {
                        window_start = left;
                        window_length = right - left + 1;
                    }
                }

                //收缩左窗
                //left是否目标串
                if (chracter_v[origin_str[left]]==0)
                {
                    target_count += 1;
                }
                chracter_v[origin_str[left]] += 1;
                left++;
            }
            //for
        }

        if (window_length == origin_str.size() + 1)
        {
            return "";
        }
        string result = origin_str.substr(window_start, window_length);
        return result;

        //------
    }
};


/*
现给定玩家的走位（例如：ASDA）,请通过更换其中一段连续走位的方式使得原走位能够变成一个完美走位
其中待更换的连续走位可以是相同长度的任何走位
请返回待更换的连续走位的最小可能长度。若果原走位本身是一个完美走位，则返回 0

输入
输入为由键盘字母表示的走位s，例如：ASDA

输出
输出为待更换的连续走位的最小可能长度

输入
AAAAADDD
输出
4
 */
class Solution02
{
public:
    Solution02(string&origin_str)
    {
        //ASDW四个字母出现的频次，应该等于total_size/4
        //统计高于4的字符，高于4的字符应该替换
        //计算包含替换字符的最小覆盖子串
        int correct_count = origin_str.size() / 4;
        unordered_map<char, int>statistic_map;
        for (auto&o_char: origin_str)
        {
            statistic_map[o_char] += 1;
        }

        vector<int>character_v(128);
        for (auto&map_item: statistic_map)
        {
            char curr_char = map_item.first;
            if (map_item.second>correct_count)
            {
                character_v[curr_char] = map_item.second - correct_count;
                target_count += (map_item.second - correct_count);
            }
        }

        if (target_count==0)
        {
            //字符频次满足条件，不需要调整
            cout << 0;
            return;
        }

        int window_length = origin_str.size() + 1;
        int left = 0;
        for (int right=0; right<origin_str.size(); right++)
        {
            char curr_char = origin_str[right];
            if (character_v[curr_char]>0)
            {
                target_count--;
            }
            character_v[curr_char] -= 1;

            while (target_count==0)
            {
                if (target_count==0)
                {
                    window_length = min(window_length, right - left + 1);

                }

                //收缩左窗
                char left_char = origin_str[left];
                if (character_v[left_char]==0)
                {
                    target_count += 1;
                }
                character_v[left_char] += 1;
                left++;
            }

            //for
        }
        cout << window_length;
        //Solution02
    }
private:
    int target_count = 0;
};


/*
 输入描述
第一行输入1个正整数N，代表明文的长度(1 <= N <= 9)
第二行输入N个明文数字组成的序列Data[i](整数，0 <= Data[i] <= 9)
第三行输入1个正整数M，(1 <= M <= 9)
接下来输入一个M*M的矩阵代表密码本Book[i][i]，(整数，0 <= Book[i][i] <= 9)

输出描述
如明文 第i位Data[i]对应密码本单元格为Book[i][j]，
则明文第i位对应的密文为X Y，X和Y之间用空格隔开。
如果有多条密文，返回字符序最小的密文。如果密码本无法匹配，返回"error"

示例1
2
0 3
3
0 0 2
1 3 4
6 6 4
输出
0 1 1 1
 */
class Solution03
{
public:
    void backTrack(vector<vector<bool>>checked, vector<vector<int>>& grid, int prev_r,int prev_c)
    {
        if (search_i==target_v.size())
        {
            result_v.push_back(track_v);
            return;
        }

        for (auto&dir_v:DirectionGrid)
        {
            int curr_r = prev_r + dir_v[0];
            int curr_c = prev_c + dir_v[1];

            //不越界，未访问，满足条件
            bool is_curr_r = curr_r >= 0 && curr_r < row_size;
            bool is_curr_c = curr_c >= 0 && curr_c < col_size;

            if (is_curr_r&&is_curr_c)
            {
                bool is_visited = checked[curr_r][curr_c];
                bool is_available = grid[curr_r][curr_c] == target_v[search_i];

                if (!is_visited && is_available)
                {
                    //做选择
                    checked[curr_r][curr_c] = true;
                    track_v.push_back(curr_r);
                    track_v.push_back(curr_c);
                    search_i++;
                    //回溯
                    backTrack(checked, grid, curr_r, curr_c);
                    //撤销选择
                    checked[curr_r][curr_c] = false;
                    track_v.pop_back();
                    track_v.pop_back();
                    search_i--;
                }
            }
            //dir_v
        }

	    //backTrack
    }
    Solution03(vector<int>&target_vec, vector<vector<int>>&grid)
    {
        row_size = grid.size();
        col_size = grid[0].size();
        target_v = target_vec;

        vector<vector<bool>>checked(row_size, vector<bool>(col_size, false));

        for (int r=0; r<row_size; r++)
        {
	        for (int c=0; c<col_size; c++)
	        {
                int curr_num = grid[r][c];
                if (curr_num==target_v[search_i])
                {
                    //做选择
                    checked[r][c] = true;
                    search_i++;
                    track_v.push_back(r);
                    track_v.push_back(c);
                    //回溯
                    backTrack(checked, grid, r, c);
                    //撤销选择
                    checked[r][c] = false;
                    search_i--;
                    track_v.pop_back();
                    track_v.pop_back();
                }

                //col_size
	        }
            //row_size
        }

        if (result_v.empty())
        {
            cout << "error";
            return;
        }

        if (result_v.size()==1)
        {
            vector<int>curr_v = result_v[0];
            for (int i=0; i<curr_v.size(); i++)
            {
                cout << curr_v[i];
                if (i!=curr_v.size()-1)
                {
                    cout << ' ';
                }
            }
            return;
        }

        vector<pair<int, string>>sort_vec;
        for (int i=0; i<result_v.size(); i++)
        {
            vector<int>curr_v = result_v[i];
            string pos_str;
            for (auto&num:curr_v)
            {
                pos_str += to_string(num);
            }
            sort_vec.push_back(make_pair(i, pos_str));
        }

        sort(sort_vec.begin(), sort_vec.end(), [](pair<int, string>& a, pair<int, string>& b)
            {
                return a.second < b.second;
            });
        //返回字符序最小的密文
        int sort_i = sort_vec[0].first;
        vector<int>curr_v = result_v[sort_i];
        for (int i = 0; i < curr_v.size(); i++)
        {
            cout << curr_v[i];
            if (i != curr_v.size() - 1)
            {
                cout << ' ';
            }
        }
        //Solution03
    }
private:
    int search_i = 0;
    int row_size = 0, col_size = 0;
    vector<int>target_v;
    vector<int>track_v;
    vector<vector<int>>result_v;
    vector<vector<int>>DirectionGrid = {{-1,0},{1,0},{0,-1},{0,1}};
};


/*
 传染病流调以及大数据分析，得到了每个人之间在时间、空间上是否存在轨迹的交叉
 现在给定一组确诊人员编号 (X1, X2, X3, ..., n)，在所有人当中，
 找出哪些人需要进行核酸检测，输出需要进行核酸检测的人数。(注意：确诊病例自身不需要再做核酸检测)
需要进行核酸检测的人，是病毒传播链条上的所有人员，即有可能通过确诊病例所能传播到的所有人。
例如：A是确诊病例，A和B有接触、B和C有接触、C和D有接触、D和E有接触，那么B\C\D\E都是需要进行核酸检测的人。

输入描述
第一行为总人数N
第二行为确诊病例人员编号(确诊病例人员数量<N)，用逗号分割
第三行开始，为一个N*N的矩阵，表示每个人员之间是否有接触，0表示没有接触，1表示有接触。

输出描述
整数：需要做核酸检测的人数

输入
5
1,2
1,1,0,1,0
1,1,0,0,0
0,0,1,0,1
1,0,0,1,0
0,0,1,0,1
输出
3

编号为1、2号的人员，为确诊病例。
1号和0号有接触，0号和3号有接触。
2号和4号有接触。
所以，需要做核酸检测的人是0号、3号、4号，总计3人需要进行核酸检测
 */
class Solution04
{
public:
    Solution04(vector<int>&search_vec, vector<vector<int>>&grid)
    {
        grid_size = grid.size();
        vector<bool>checked(grid_size, false);
        deque<int>bfs_queue;
        for (auto&num:search_vec)
        {
            checked[num] = true;
            search_set.insert(num);
            bfs_queue.push_back(num);
        }

        while (!bfs_queue.empty())
        {
            int top_node = bfs_queue.front();
            bfs_queue.pop_front();

            result_vec.push_back(top_node);
            vector<int>link_vec = grid[top_node];

            //i!=top_node 未访问 符合要求 入队列
            for (int i=0; i<grid_size; i++)
            {
	            if (i!=top_node)
	            {
                    bool is_visited = checked[i];
                    bool is_available = link_vec[i] == 1;

                    if (!is_visited&& is_available)
                    {
                        //标记已访问
                        checked[i] = true;
                        bfs_queue.push_back(i);
                    }

	            }
            }

            //while (!bfs_queue.empty())
        }

        int result = 0;
        for (auto&num:result_vec)
        {
	        if (search_set.count(num)==0)
	        {
                result += 1;
	        }
        }

        cout << result;
	    //Solution04
    }
private:
    int grid_size = 0;
    vector<int>result_vec;
    unordered_set<int>search_set;
};


int main()
{
	{
/*
5
1,2
1,1,0,1,0
1,1,0,0,0
0,0,1,0,1
1,0,0,1,0
0,0,1,0,1
*/
        int grid_size;
        cin >> grid_size;
        cin.ignore();

        string input;
        getline(cin, input);
        stringstream search_sstream(input);
        string token;

        vector<int>search_v;
        while (getline(search_sstream,token,','))
        {
            search_v.push_back(stoi(token));
        }

        vector<vector<int>>grid;
        for (int i=0; i<grid_size; i++)
        {
            vector<int>min_vec;
            getline(cin, input);
            stringstream grid_sstream(input);

            while (getline(grid_sstream,token,','))
            {
                min_vec.push_back(stoi(token));
            }
            grid.push_back(min_vec);
        }

        Solution04 solu(search_v, grid);

        return 0;
	}
	{
/*
2
0 3
3
0 0 2
1 3 4
6 6 4
*/
        int target_size;
        cin >> target_size;
        vector<int>target_vec(target_size);

        for (int i=0; i<target_size; i++)
        {
            cin >> target_vec[i];
        }

        int grid_size;
        cin >> grid_size;
        vector<vector<int>>grid(grid_size,vector<int>(grid_size));

        for (int r=0; r<grid_size; r++)
        {
	        for (int c=0; c<grid_size;c++)
	        {
                cin >> grid[r][c];
	        }
        }

        Solution03 solu(target_vec, grid);

        return 0;
	}
	{
        //string input = "AAAAADDD";
        string input;
        getline(cin, input);
        Solution02 solu(input);

        return 0;
	}
    string s = "ADOBECODEBANC", t = "ABC";

    Solution01 solu;
    cout << solu.minWindow(s, t);

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
